#include <iostream>
#include <algorithm>
#include <vector>
#include <map>
#include <queue>
using namespace std;
#define int long long 
#define pii pair<int,int>
const int MAXN = 1e6 + 10;
int n, cnt = 0;
int x1, y1, x2, y2, x[MAXN << 1];
struct node {
	int l, r, h, k;
	bool operator<(const node& x)const {
		return h < x.h;
	}
};

node line[MAXN << 1];





//#define pdd pair<long double,long double>
//#define x first
//#define y second
//
//constexpr double eps = 1e-6;
//double sum;
//double tp = 0;
//bool chk(pdd& l, pdd& r, pdd& k) {
//    if (k.x<min(l.x, r.x) || k.x>max(l.x, r.x)) {
//        return false;
//    }
//    if (k.y<min(l.y, r.y) || k.y>max(l.y, r.y)) {
//        return false;
//    }
//    if (abs((l.y - k.y) * (r.x - k.x) - (r.y - k.y) * (l.x - k.x)) < eps) {
//        return true;
//    }
//    return false;
//}
//double s(pdd& o, pdd& l, pdd& r) {
//    return abs((l.x - o.x) * (r.y - o.y) - (r.x - o.x) * (l.y - o.y)) / 2;
//}
//int check(pdd& o, pdd& l, pdd& r, pdd& t) {
//    if ((s(o, l, t) - s(o, t, r) - tp) / sum > eps) return -1;
//    if ((s(o, l, t) - s(o, t, r) - tp) / sum < -eps) return 1;
//    return 0;
//}
//pair<int, int> a[5];
//pdd p[5];
//signed main() {
//    std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
//    int t; cin >> t;
//    while (t--) {
//        for (int i = 1; i <= 4; ++i) {
//            cin >> a[i].x >> a[i].y;
//        }
//        if (a[1].x == a[4].x && a[1].y == a[4].y) {
//            cout << (a[2].x + a[3].x) / 2.0 << ' ' << ((a[2].y + a[3].y) / 2.0) << endl;
//            continue;
//        }
//        if (a[2].x == a[4].x && a[2].y == a[4].y) {
//            cout << (a[1].x + a[3].x) / 2.0 << ' ' << ((a[1].y + a[3].y) / 2.0) << endl;
//            continue;
//        }
//        if (a[3].x == a[4].x && a[3].y == a[4].y) {
//            cout << (a[1].x + a[2].x) / 2.0 << ' ' << ((a[1].y + a[2].y) / 2.0) << endl;
//            continue;
//        }
//        for (int i = 1; i <= 4; ++i) {
//            p[i].x = a[i].x;
//            p[i].y = a[i].y;
//        }
//        sum = s(p[1], p[2], p[3]);
//        bool o = true;
//        for (int i = 1; i <= 3; ++i) {
//            if (i == 2) swap(p[1], p[3]);
//            if (i == 3) swap(p[2], p[3]);
//            if (chk(p[1], p[2], p[4])) {
//                o = false;
//                tp = 0;
//                int e = check(p[4], p[1], p[2], p[3]);
//                if (e == 0) {
//                    cout << p[3].x << ' ' << p[3].y << endl;
//                }
//                else if (e == -1) {
//                    tp = s(p[4], p[2], p[3]);
//                    pdd l = p[1], r = p[3];
//                    double ll = 0, rr = 1;
//                    pdd t;
//                    while (abs(rr - ll) > eps) {
//                        double mid = (ll + rr) / 2;
//                        t = { mid * l.x + (1 - mid) * r.x,mid * l.y + (1 - mid) * r.y };
//                        int h = check(p[4], l, r, t);
//                        if (h == 0) break;
//                        else if (h == 1) {
//                            rr = mid;
//                        }
//                        else ll = mid;
//                    }
//                    cout << t.x << ' ' << t.y << endl;
//                }
//                else {
//                    pdd l = p[2], r = p[3];
//                    tp = s(p[4], p[1], p[3]);
//                    double ll = 0, rr = 1;
//                    pdd t;
//                    while (abs(rr - ll) > eps) {
//                        double mid = (ll + rr) / 2;
//                        t = { mid * l.x + (1 - mid) * r.x,mid * l.y + (1 - mid) * r.y };
//                        int h = check(p[4], l, r, t);
//                        if (h == 0) break;
//                        else if (h == 1) {
//                            rr = mid;
//                        }
//                        else ll = mid;
//                    }
//                    cout << t.x << ' ' << t.y << endl;
//                }
//                break;
//            }
//        }
//        if (o) cout << -1 << endl;
//    }
//}

//
//const int mod = 1e9 + 7;
//
//int n, m;
//int a[1005][1005];
//int dx[4] = { 0,0,1,-1 };
//int dy[4] = { 1,-1,0,0 };
//int ans;
//int dp[1005][1005][5];
//int in[1005][1005];
//int out[1005][1005];
//queue<pii> q;
//
//void solve() {
//	cin >> n >> m;
//	for (int i = 1; i <= n; i++) {
//		for (int j = 1; j <= m; j++) {
//			cin >> a[i][j];
//		}
//	}
//	for (int i = 1; i <= n; i++) {
//		for (int j = 1; j <= m; j++) {
//			for (int k = 0; k < 4; k++) {
//				int xx = i + dx[k], yy = j + dy[k];
//				if (0 < xx && xx <= n && 0 < yy && yy <= m) {
//					if (a[xx][yy] == a[i][j] + 1)out[i][j]++;
//					if (a[xx][yy] == a[i][j] - 1)in[i][j]++;
//				}
//			}
//		}
//	}
//	for (int i = 1; i <= n; i++) {
//		for (int j = 1; j <= m; j++) {
//			if (!in[i][j]) {
//				q.push({ i,j });
//				dp[i][j][1] = 1;
//			}
//		}
//	}
//	while (!q.empty()) {
//		int x = q.front().first, y = q.front().second; q.pop();
//		for (int i = 0; i < 4; i++) {
//			int xx = x + dx[i], yy = y + dy[i];
//			if (0 < xx && xx <= n && 0 < yy && yy <= m) {
//				if (a[xx][yy] == a[x][y] + 1) {
//					dp[xx][yy][2] = (dp[xx][yy][2] + dp[x][y][1]) % mod;
//					dp[xx][yy][3] = (dp[xx][yy][3] + dp[x][y][2]) % mod;
//					dp[xx][yy][4] = (dp[xx][yy][4] + dp[x][y][3] + dp[x][y][4]) % mod;
//					in[xx][yy]--;
//					if (!in[xx][yy])q.push({ xx,yy });
//				}
//			}
//		}
//	}
//	for (int i = 1; i <= n; i++) {
//		for (int j = 1; j <= m; j++) {
//			if (!out[i][j]) {
//				ans = (ans + dp[i][j][4]) % mod;
//			}
//		}
//	}
//	cout << ans << '\n';
//}

//bool checked(int x, int y) {
//	for (int i = 0; i < 4; i++) {
//		int xx = x + dx[i], yy = y + dy[i];
//		if (a[xx][yy] == a[x][y] + 1)
//			return false;
//	}
//	return true;
//}
//void solve() {
//	cin >> n >> m;
//	for (int i = 1; i <= n; i++) {
//		for (int j = 1; j <= m; j++) {
//			cin >> a[i][j];
//		}
//	}
//	for (int i = 1; i <= n; i++) {
//		for (int j = 1; j <= m; j++) {
//			for (int k = 0; k < 4; k++) {
//				int xx = i + dx[i], yy = j + dy[i];
//				bool st = true;
//				if (0 < xx && xx <= n && 0 < yy && yy <= m) {
//					if (a[xx][yy] == a[i][j] - 1) {
//						st = false;
//						break;
//					}
//				}
//				if (st) {
//					q.push({ i,j });
//					be.push(a[i][j]);
//					cnt[i][j] = 1;
//				}
//			}
//		}
//	}
//
//	while (!q.empty()) {
//		int x = q.front().first, y = q.front().second; q.pop();
//		int st = be.front(); be.pop();
//		for (int i = 0; i < 4; i++) {
//			int xx = x + dx[i], yy = y + dy[i];
//			if (0 < xx && xx <= n && 0 < yy && yy <= m) {
//				if (a[xx][yy] == a[x][y] + 1) {
//					cnt[xx][yy] += cnt[x][y];
//					if (in[xx][yy])continue;
//					q.push({ xx,yy });
//					in[xx][yy] = 1;
//				}
//			}
//		}
//	}
//
//
//	int ans = 0;
//	for (int i = 1; i <= n; i++) {
//		for (int j = 1; j <= m; j++) {
//			if (ok[i][j])
//				ans += cnt[i][j];
//		}
//	}
//	cout << ans << '\n';
//}

//int n, w;
//int a[20];
//int ans;
//int cab[20];
//
//void dfs(int now, int cnt) {
//	if (cnt >= ans)return;
//	if (now == n + 1) {
//		ans = min(ans, cnt);
//		return;
//	}
//	for (int i = 1; i <= cnt; i++) {
//		if (cab[i] + a[now] <= w) {
//			cab[i] += a[now];
//			dfs(now + 1, cnt);
//			cab[i] -= a[now];
//		}
//	}
//	cab[cnt + 1] = a[now];
//	dfs(now + 1, cnt + 1);
//	cab[cnt + 1] = 0;
//
//}
//
//void solve() {
//	cin >> n >> w;
//	for (int i = 1; i <= n; i++) {
//		cin >> a[i];
//	}
//	ans = n;
//	sort(a + 1, a + 1 + n, [&](int a, int b) {return a > b; });
//	dfs(1, 0);
//	cout << ans << '\n';
//}

//int n, m;
//int l, r;
//int a[1000006];
//
//void solve() {
//	cin >> n >> m;
//	for (int i = 1; i <= n; i++) {
//		cin >> a[i];
//	}
//	map<int, int> mp;
//	int L = 0, R = 1e9;
//	for (int l = 1, r = 1; r <= n; r++) {
//		mp[a[r]]++;
//		if (mp.size() == m) {
//			while (mp.size() == m) {
//				mp[a[l]]--;
//				if (mp[a[l]] == 0)
//					mp.erase(a[l]);
//				l++;
//			}
//			if (r - l + 1 < R - L) {
//				R = r;
//				L = l - 1;
//			}
//		}
//	}
//	cout << L << ' ' << R << '\n';
//}